<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>Navo Portable Library: navo/algorithm/nonlinear/binary/avllnk.h源文件</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body onload='searchBox.OnSelectItem(0);'>
<!-- 制作者 Doxygen 1.7.3 -->
<script type="text/javascript"><!--
var searchBox = new SearchBox("searchBox", "search",false,'搜索');
--></script>
<div id="top">
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td style="padding-left: 0.5em;">
   <div id="projectname">Navo Portable Library&#160;<span id="projectnumber">Ver 1.0.20120827</span></div>
   <div id="projectbrief">Provides generic platform independent facilities.</div>
  </td>
 </tr>
 </tbody>
</table>
</div>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>首页</span></a></li>
      <li><a href="modules.html"><span>模块</span></a></li>
      <li><a href="annotated.html"><span>数据结构</span></a></li>
      <li class="current"><a href="files.html"><span>文件</span></a></li>
      <li id="searchli">
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="搜索" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="files.html"><span>文件列表</span></a></li>
      <li><a href="globals.html"><span>全局定义</span></a></li>
    </ul>
  </div>
<div class="header">
  <div class="headertitle">
<h1>navo/algorithm/nonlinear/binary/avllnk.h</h1>  </div>
</div>
<div class="contents">
<a href="avllnk_8h.html">浏览该文件的文档。</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */</span>
<a name="l00011"></a>00011 <span class="preprocessor">#ifdef _MSC_VER</span>
<a name="l00012"></a>00012 <span class="preprocessor"></span><span class="preprocessor">#pragma once</span>
<a name="l00013"></a>00013 <span class="preprocessor"></span><span class="preprocessor">#endif </span><span class="comment">/* #ifdef _MSC_VER */</span>
<a name="l00014"></a>00014 
<a name="l00015"></a>00015 <span class="preprocessor">#ifndef __NV_AVLLNK__</span>
<a name="l00016"></a>00016 <span class="preprocessor"></span><span class="preprocessor">#define __NV_AVLLNK__</span>
<a name="l00017"></a>00017 <span class="preprocessor"></span>
<a name="l00018"></a>00018 <span class="preprocessor">#include &quot;<a class="code" href="cdef_8h.html" title="Definitions and declarations for common constants, types, variables.">../../../port/cdef.h</a>&quot;</span>
<a name="l00019"></a>00019 <span class="preprocessor">#include &quot;<a class="code" href="integer_8h.html" title="Provides standard integer types.">../../../port/integer.h</a>&quot;</span>
<a name="l00020"></a>00020 
<a name="l00021"></a>00021 <span class="preprocessor">#ifdef __cplusplus</span>
<a name="l00022"></a>00022 <span class="preprocessor"></span><span class="keyword">extern</span> <span class="stringliteral">&quot;C&quot;</span> {
<a name="l00023"></a>00023 <span class="preprocessor">#endif  </span><span class="comment">/* #ifdef __cplusplus */</span>
<a name="l00024"></a>00024 
<a name="l00031"></a>00031 <span class="preprocessor">#if defined(_MSC_VER) || defined(__CYGWIN__)</span>
<a name="l00032"></a>00032 <span class="preprocessor"></span><span class="preprocessor">#pragma pack(push, 4)</span>
<a name="l00033"></a>00033 <span class="preprocessor"></span><span class="preprocessor">#endif </span><span class="comment">/* #if defined(_MSC_VER) || defined(__CYGWIN__) */</span>
<a name="l00034"></a>00034 
<a name="l00043"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga110276c151b52a9e937f120f863cb34b">00043</a> <span class="keyword">typedef</span> <span class="keyword">struct </span>intrin_align(4) <a class="code" href="struct____avllnk__node.html" title="AVL树节点">__avllnk_node</a>{
<a name="l00045"></a>00045     uintptr_t parent_height;
<a name="l00047"></a>00047     <span class="keyword">struct </span><a class="code" href="struct____avllnk__node.html" title="AVL树节点">__avllnk_node</a>* left;
<a name="l00049"></a>00049     <span class="keyword">struct </span><a class="code" href="struct____avllnk__node.html" title="AVL树节点">__avllnk_node</a>* right;
<a name="l00050"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gada1586d3a852e7d13f51543c09ac5a58">00050</a> }<a class="code" href="group__AVL_xE6_xA0_x91.html#gada1586d3a852e7d13f51543c09ac5a58" title="节点">avllnk_node</a>, *<a class="code" href="group__AVL_xE6_xA0_x91.html#ga391ef925a6daa3822e079a4848543426" title="迭代器">avllnk_iter</a>;
<a name="l00051"></a>00051 
<a name="l00052"></a>00052 <span class="preprocessor">#if defined(_MSC_VER) || defined(__CYGWIN__)</span>
<a name="l00053"></a>00053 <span class="preprocessor"></span><span class="preprocessor">#pragma pack(pop)</span>
<a name="l00054"></a>00054 <span class="preprocessor"></span><span class="preprocessor">#endif </span><span class="comment">/* #if defined(_MSC_VER) || defined(__CYGWIN__) */</span>
<a name="l00055"></a>00055 
<a name="l00056"></a>00056 <span class="preprocessor">#define AVLLNK_LH       0   </span><span class="comment">/* 左子树高 */</span>
<a name="l00057"></a>00057 <span class="preprocessor">#define AVLLNK_RH       1   </span><span class="comment">/* 右子树高 */</span>
<a name="l00058"></a>00058 <span class="preprocessor">#define AVLLNK_BL       3   </span><span class="comment">/* 子树平衡 */</span>
<a name="l00059"></a>00059 <span class="preprocessor">#define AVLLNK_MASK     3   </span><span class="comment">/* 高度信息掩码 */</span>
<a name="l00060"></a>00060 
<a name="l00065"></a><a class="code" href="structavllnk__root.html">00065</a> <span class="keyword">typedef</span> <span class="keyword">struct </span>{
<a name="l00067"></a><a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff">00067</a>     <a class="code" href="group__AVL_xE6_xA0_x91.html#gada1586d3a852e7d13f51543c09ac5a58" title="节点">avllnk_node</a>* <a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a>;
<a name="l00068"></a>00068 }<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>;
<a name="l00069"></a>00069 
<a name="l00074"></a><a class="code" href="structavllnk__info.html">00074</a> <span class="keyword">typedef</span> <span class="keyword">struct </span>{
<a name="l00076"></a><a class="code" href="structavllnk__info.html#a76d971a3c552bc58ba9f0d5fceae9806">00076</a>     <span class="keywordtype">size_t</span> <a class="code" href="structavllnk__info.html#a76d971a3c552bc58ba9f0d5fceae9806" title="节点数">count</a>;
<a name="l00078"></a><a class="code" href="structavllnk__info.html#a820c167ceaaa9759b0ca2695d22db55c">00078</a>     <span class="keywordtype">size_t</span> <a class="code" href="structavllnk__info.html#a820c167ceaaa9759b0ca2695d22db55c" title="深度">depth</a>;
<a name="l00080"></a><a class="code" href="structavllnk__info.html#a62f3b2ad4f6c6147d1bb9a71dd8c9656">00080</a>     <span class="keywordtype">size_t</span> <a class="code" href="structavllnk__info.html#a62f3b2ad4f6c6147d1bb9a71dd8c9656" title="叶子数">leafs</a>;
<a name="l00081"></a>00081 }<a class="code" href="structavllnk__info.html" title="树信息表">avllnk_info</a>;
<a name="l00082"></a>00082 
<a name="l00094"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga9f935129e3b1b42561ef2b542ddc8c16">00094</a> <span class="preprocessor">#define AVLLNK_ROOT(name) avllnk_root name = {NULL}</span>
<a name="l00095"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gad23c26b8eb6162eb970bc21c23072bc9">00095</a> <span class="preprocessor"></span><span class="preprocessor">#define AVLLNK_NODE(name) avllnk_node name = {0, NULL, NULL}</span>
<a name="l00096"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga46bf7c9e6c92af98442241e46bc0fb6e">00096</a> <span class="preprocessor"></span><span class="preprocessor">#define AVLLNK_INFO(name) avllnk_info name = {0, 0, 0}</span>
<a name="l00097"></a>00097 <span class="preprocessor"></span>
<a name="l00104"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga6d7aaed44e837466148513a1e9c4b055">00104</a> <span class="keyword">typedef</span> int (*<a class="code" href="group__AVL_xE6_xA0_x91.html#ga6d7aaed44e837466148513a1e9c4b055" title="单参数回调函数指针">avllnk_pr1</a>)(<a class="code" href="group__AVL_xE6_xA0_x91.html#gada1586d3a852e7d13f51543c09ac5a58" title="节点">avllnk_node</a>*);
<a name="l00105"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gab87ebf52c2b6245bb72eb9acae29a644">00105</a> <span class="keyword">typedef</span> int (*<a class="code" href="group__AVL_xE6_xA0_x91.html#gab87ebf52c2b6245bb72eb9acae29a644" title="双参数回调函数指针">avllnk_pr2</a>)(<a class="code" href="group__AVL_xE6_xA0_x91.html#gada1586d3a852e7d13f51543c09ac5a58" title="节点">avllnk_node</a>*, avllnk_node*);
<a name="l00106"></a>00106 
<a name="l00114"></a>00114 NV_API <span class="keywordtype">size_t</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga05210b7a523aff433666c4b6c7fec4b4" title="获取树的节点总数">avllnk_count</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root);
<a name="l00115"></a>00115 
<a name="l00124"></a>00124 NV_API <span class="keywordtype">size_t</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gaeb29658f08fdd8c607c2f04a2dd9afd5" title="计算两个节点的迭代距离">avllnk_distance</a>(avllnk_iter first, avllnk_iter last);
<a name="l00125"></a>00125 
<a name="l00134"></a>00134 NV_API <span class="keywordtype">size_t</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gaa2e635167aec956c163f38e293006b06" title="计算迭代器的正向索引">avllnk_index_of</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, avllnk_iter itr);
<a name="l00135"></a>00135 
<a name="l00144"></a>00144 NV_API <span class="keywordtype">size_t</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga3a272f8492a0090feeb1bf4552b7535b" title="计算迭代器的逆向索引">avllnk_reverse_index_of</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, avllnk_iter itr);
<a name="l00145"></a>00145 
<a name="l00153"></a>00153 NV_API <span class="keywordtype">size_t</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga584d9cf0d557e45fac9ac792967ecd38" title="计算树的深度">avllnk_depth</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root);
<a name="l00154"></a>00154 
<a name="l00162"></a>00162 NV_API <span class="keywordtype">size_t</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga0bdae474b1779392de944dbe1eee2d0c" title="计算树的叶子数">avllnk_leafs</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root);
<a name="l00163"></a>00163 
<a name="l00171"></a>00171 NV_API <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga9edbfa0855053c7f9bbd4d6e8a86199d" title="获取树的信息，包括节点数、深度、叶子数">avllnk_get_info</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, <a class="code" href="structavllnk__info.html" title="树信息表">avllnk_info</a>* info);
<a name="l00172"></a>00172 
<a name="l00216"></a>00216 NV_API <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga8d0cac80915509c752cfceebce741037" title="插入节点后，对树进行再平衡调整">avllnk_rebalance</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, avllnk_node* node, 
<a name="l00217"></a>00217                                 avllnk_node* parent);
<a name="l00218"></a>00218 
<a name="l00225"></a>00225 NV_API <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gaf66cbfca9147bf2de3109b0792242c6b" title="移除某个节点">avllnk_erase</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, avllnk_node* entry);
<a name="l00226"></a>00226 
<a name="l00240"></a>00240 NV_API <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga062945f5da72bea1f96c1e79b14ee1d6" title="移除区域内的节点">avllnk_erases</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, avllnk_iter begin, 
<a name="l00241"></a>00241                             avllnk_iter end, <a class="code" href="group__AVL_xE6_xA0_x91.html#ga6d7aaed44e837466148513a1e9c4b055" title="单参数回调函数指针">avllnk_pr1</a> erase_handler);
<a name="l00242"></a>00242 
<a name="l00254"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gaaed45fd00cc292f5a5ae11c5939b75af">00254</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gaaed45fd00cc292f5a5ae11c5939b75af" title="初始化树根">avllnk_init</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root)
<a name="l00255"></a>00255 {
<a name="l00256"></a>00256     root-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a> = NULL;
<a name="l00257"></a>00257 }
<a name="l00258"></a>00258 
<a name="l00273"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gaed7a979e936d126bdfcb326e7c341853">00273</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gaed7a979e936d126bdfcb326e7c341853" title="判断树是否为空">avllnk_empty</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root)
<a name="l00274"></a>00274 {
<a name="l00275"></a>00275     <span class="keywordflow">return</span> !root-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a>;
<a name="l00276"></a>00276 }
<a name="l00277"></a>00277 
<a name="l00278"></a>00278 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> __avllnk_singular(avllnk_node* root)
<a name="l00279"></a>00279 {
<a name="l00280"></a>00280     <span class="keywordflow">return</span> root &amp;&amp; !root-&gt;left &amp;&amp; !root-&gt;right;
<a name="l00281"></a>00281 }
<a name="l00282"></a>00282 
<a name="l00297"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga818841161a46f54d53529773eb96bacd">00297</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga818841161a46f54d53529773eb96bacd" title="判断树是否只有单个节点">avllnk_singular</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root)
<a name="l00298"></a>00298 {
<a name="l00299"></a>00299     <span class="keywordflow">return</span> __avllnk_singular(root-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a>);
<a name="l00300"></a>00300 }
<a name="l00301"></a>00301 
<a name="l00331"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gaf8e74e1e8ecd70501d3b4d5fac912f0c">00331</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gaf8e74e1e8ecd70501d3b4d5fac912f0c" title="判断树是否可以序列化">avllnk_serialable</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root)
<a name="l00332"></a>00332 {
<a name="l00333"></a>00333     <span class="keywordflow">return</span> !!root-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a>;
<a name="l00334"></a>00334 }
<a name="l00335"></a>00335 
<a name="l00343"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gac186538077a32ca88a0b0fb38c7748ee">00343</a> <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#gac186538077a32ca88a0b0fb38c7748ee" title="得到左子节点">avllnk_left</a>(avllnk_node* node)
<a name="l00344"></a>00344 {
<a name="l00345"></a>00345     <span class="keywordflow">return</span> node-&gt;left;
<a name="l00346"></a>00346 }
<a name="l00347"></a>00347 
<a name="l00355"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga392cad63ddf7750b67b0296c6b27e358">00355</a> <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#ga392cad63ddf7750b67b0296c6b27e358" title="得到右子节点">avllnk_right</a>(avllnk_node* node)
<a name="l00356"></a>00356 {
<a name="l00357"></a>00357     <span class="keywordflow">return</span> node-&gt;right;
<a name="l00358"></a>00358 }
<a name="l00359"></a>00359 
<a name="l00366"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga691c39005f3bf2afc370f10c4e7d98f1">00366</a> <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#ga691c39005f3bf2afc370f10c4e7d98f1" title="得到父节点">avllnk_parent</a>(avllnk_node* node)
<a name="l00367"></a>00367 {
<a name="l00368"></a>00368     <span class="keywordflow">return</span> (avllnk_iter)(node-&gt;parent_height &amp; (~AVLLNK_MASK));
<a name="l00369"></a>00369 }
<a name="l00370"></a>00370 
<a name="l00380"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gaa8353ffe957c498dc63929ed50ee4cf5">00380</a> <span class="keyword">static</span> <span class="keyword">inline</span> uintptr_t <a class="code" href="group__AVL_xE6_xA0_x91.html#gaa8353ffe957c498dc63929ed50ee4cf5" title="得到节点的高度值">avllnk_height</a>(avllnk_node* node)
<a name="l00381"></a>00381 {
<a name="l00382"></a>00382     <span class="keywordflow">return</span> (node-&gt;parent_height &amp; AVLLNK_MASK);
<a name="l00383"></a>00383 }
<a name="l00384"></a>00384 
<a name="l00393"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga8ee3f2da09ef4b7d1c00610b3372a01f">00393</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga8ee3f2da09ef4b7d1c00610b3372a01f" title="判断节点是否是左子树高">avllnk_left_high</a>(avllnk_node* node)
<a name="l00394"></a>00394 {
<a name="l00395"></a>00395     <span class="keywordflow">return</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gaa8353ffe957c498dc63929ed50ee4cf5" title="得到节点的高度值">avllnk_height</a>(node) == AVLLNK_LH;
<a name="l00396"></a>00396 }
<a name="l00397"></a>00397 
<a name="l00406"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga04edcfd65b742a3382b3a51eef68f307">00406</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga04edcfd65b742a3382b3a51eef68f307" title="判断节点是否是右子树高">avllnk_right_high</a>(avllnk_node* node)
<a name="l00407"></a>00407 {
<a name="l00408"></a>00408     <span class="keywordflow">return</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gaa8353ffe957c498dc63929ed50ee4cf5" title="得到节点的高度值">avllnk_height</a>(node) == AVLLNK_RH;
<a name="l00409"></a>00409 }
<a name="l00410"></a>00410 
<a name="l00419"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga364ee370c34025c9318833ee20965759">00419</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga364ee370c34025c9318833ee20965759" title="判断节点是否是平衡的">avllnk_balanced</a>(avllnk_node* node)
<a name="l00420"></a>00420 {
<a name="l00421"></a>00421     <span class="keywordflow">return</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gaa8353ffe957c498dc63929ed50ee4cf5" title="得到节点的高度值">avllnk_height</a>(node) == AVLLNK_BL;
<a name="l00422"></a>00422 }
<a name="l00423"></a>00423 
<a name="l00432"></a>00432  */
<a name="l00433"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gacfb27f0b831d3c4f83381c6b0956106f">00433</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gacfb27f0b831d3c4f83381c6b0956106f" title="判断当前节点是否是根节点">avllnk_is_root</a>(avllnk_iter itr)
<a name="l00434"></a>00434 {
<a name="l00435"></a>00435     <span class="keywordflow">return</span> !<a class="code" href="group__AVL_xE6_xA0_x91.html#ga691c39005f3bf2afc370f10c4e7d98f1" title="得到父节点">avllnk_parent</a>(itr);
<a name="l00436"></a>00436 }
<a name="l00437"></a>00437 
<a name="l00446"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga64ef8761a0fab06321833ee0158ab196">00446</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga64ef8761a0fab06321833ee0158ab196" title="判断当前节点是否是叶子节点">avllnk_is_leaf</a>(avllnk_iter itr)
<a name="l00447"></a>00447 {
<a name="l00448"></a>00448     <span class="keywordflow">return</span> !itr-&gt;left &amp;&amp; !itr-&gt;right;
<a name="l00449"></a>00449 }
<a name="l00450"></a>00450 
<a name="l00462"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gac43ae3a0dc2bf5d7da2a526d55397fe7">00462</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gac43ae3a0dc2bf5d7da2a526d55397fe7" title="链接两个节点">avllnk_link</a>(avllnk_iter newly, avllnk_iter parent, 
<a name="l00463"></a>00463                                 avllnk_iter* plink)
<a name="l00464"></a>00464 {
<a name="l00465"></a>00465     <span class="comment">/* 简单地将newly节点链接到parent节点下 */</span>
<a name="l00466"></a>00466     *plink = newly;
<a name="l00467"></a>00467     newly-&gt;left = NULL;
<a name="l00468"></a>00468     newly-&gt;right = NULL;
<a name="l00469"></a>00469     <span class="comment">/* 新节点默认是平衡的 */</span>
<a name="l00470"></a>00470     newly-&gt;parent_height = ((uintptr_t)parent) | AVLLNK_BL;
<a name="l00471"></a>00471 }
<a name="l00472"></a>00472 
<a name="l00478"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga2089ba17ce26c8762a19c614a8d06555">00478</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga2089ba17ce26c8762a19c614a8d06555" title="设置当前节点高度为左子树高">avllnk_set_left_high</a>(avllnk_node* node)
<a name="l00479"></a>00479 {
<a name="l00480"></a>00480     node-&gt;parent_height &amp;= (~AVLLNK_MASK);
<a name="l00481"></a>00481 }
<a name="l00482"></a>00482 
<a name="l00488"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga09a24ae32f166f358df10788e0f7c284">00488</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga09a24ae32f166f358df10788e0f7c284" title="设置当前节点高度为右子树高">avllnk_set_right_high</a>(avllnk_node* node)
<a name="l00489"></a>00489 {
<a name="l00490"></a>00490     node-&gt;parent_height = AVLLNK_RH | 
<a name="l00491"></a>00491         (node-&gt;parent_height &amp; (~AVLLNK_MASK));
<a name="l00492"></a>00492 }
<a name="l00493"></a>00493 
<a name="l00499"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga7d074b83d26dcadffe3833166a9c048a">00499</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga7d074b83d26dcadffe3833166a9c048a" title="设置当前节点为平衡节点">avllnk_set_balanced</a>(avllnk_node* node)
<a name="l00500"></a>00500 {
<a name="l00501"></a>00501     node-&gt;parent_height |= AVLLNK_MASK;
<a name="l00502"></a>00502 }
<a name="l00503"></a>00503 
<a name="l00511"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gafb7ce3c4fbef8c022feae53e69f2e4ec">00511</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gafb7ce3c4fbef8c022feae53e69f2e4ec" title="设置当前节点的父节点">avllnk_set_parent</a>(avllnk_node* node, 
<a name="l00512"></a>00512                                         avllnk_node* parent)
<a name="l00513"></a>00513 {
<a name="l00514"></a>00514     node-&gt;parent_height = (uintptr_t)(parent) | 
<a name="l00515"></a>00515         (node-&gt;parent_height &amp; AVLLNK_MASK);
<a name="l00516"></a>00516 }
<a name="l00517"></a>00517 
<a name="l00525"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga546ae7404c5213a86aa721036babceff">00525</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga546ae7404c5213a86aa721036babceff" title="仅在node不为空时，设置node的父节点">avllnk_set_parent_if</a>(avllnk_node* node, 
<a name="l00526"></a>00526                                     avllnk_node* parent)
<a name="l00527"></a>00527 {
<a name="l00528"></a>00528     <span class="keywordflow">if</span> (node)
<a name="l00529"></a>00529         <a class="code" href="group__AVL_xE6_xA0_x91.html#gafb7ce3c4fbef8c022feae53e69f2e4ec" title="设置当前节点的父节点">avllnk_set_parent</a>(node, parent);
<a name="l00530"></a>00530 }
<a name="l00531"></a>00531 
<a name="l00543"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga960f9f58b12e793793f259d9340926c9">00543</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga960f9f58b12e793793f259d9340926c9" title="同时设置节点的父节点和高度值">avllnk_set_parent_height</a>(avllnk_node* node, 
<a name="l00544"></a>00544                             avllnk_node* parent, uintptr_t height)
<a name="l00545"></a>00545 {
<a name="l00546"></a>00546     node-&gt;parent_height = (uintptr_t)(parent) | height;
<a name="l00547"></a>00547 }
<a name="l00548"></a>00548 
<a name="l00554"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga968f04fff9bef8e27bf36936e929a545">00554</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga968f04fff9bef8e27bf36936e929a545" title="初始化节点">avllnk_node_init</a>(avllnk_node* node)
<a name="l00555"></a>00555 {
<a name="l00556"></a>00556     node-&gt;parent_height = 0;
<a name="l00557"></a>00557     node-&gt;left = NULL;
<a name="l00558"></a>00558     node-&gt;right = NULL;
<a name="l00559"></a>00559 }
<a name="l00560"></a>00560 
<a name="l00569"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga016a1b1accea2b6145fa189bfd119507">00569</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga016a1b1accea2b6145fa189bfd119507" title="用新节点替换旧节点">avllnk_iter_replace</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, 
<a name="l00570"></a>00570                             avllnk_iter victim,  avllnk_iter newly)
<a name="l00571"></a>00571 {
<a name="l00572"></a>00572     avllnk_iter parent = <a class="code" href="group__AVL_xE6_xA0_x91.html#ga691c39005f3bf2afc370f10c4e7d98f1" title="得到父节点">avllnk_parent</a>(victim);
<a name="l00573"></a>00573     
<a name="l00574"></a>00574     <span class="comment">/* 将victim父节点的孩子设为newly */</span>
<a name="l00575"></a>00575     <span class="keywordflow">if</span> (parent) {
<a name="l00576"></a>00576         <span class="keywordflow">if</span> (victim == parent-&gt;left)
<a name="l00577"></a>00577             parent-&gt;left = newly;
<a name="l00578"></a>00578         <span class="keywordflow">else</span>
<a name="l00579"></a>00579             parent-&gt;right = newly;
<a name="l00580"></a>00580     } <span class="keywordflow">else</span>
<a name="l00581"></a>00581         root-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a> = newly;
<a name="l00582"></a>00582     
<a name="l00583"></a>00583     <span class="comment">/* 重新确定victim孩子节点的父节点为newly */</span>
<a name="l00584"></a>00584     <a class="code" href="group__AVL_xE6_xA0_x91.html#ga546ae7404c5213a86aa721036babceff" title="仅在node不为空时，设置node的父节点">avllnk_set_parent_if</a>(victim-&gt;left, newly);
<a name="l00585"></a>00585     <a class="code" href="group__AVL_xE6_xA0_x91.html#ga546ae7404c5213a86aa721036babceff" title="仅在node不为空时，设置node的父节点">avllnk_set_parent_if</a>(victim-&gt;right, newly);
<a name="l00586"></a>00586     
<a name="l00587"></a>00587     <span class="comment">/* 替换节点成员 */</span>
<a name="l00588"></a>00588     *newly = *victim;
<a name="l00589"></a>00589 }
<a name="l00590"></a>00590 
<a name="l00597"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga5f22b54f9ef02ade099fe28889e327b6">00597</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga5f22b54f9ef02ade099fe28889e327b6" title="用新的树根替换旧树根">avllnk_replace</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* victim, <a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* newly)
<a name="l00598"></a>00598 {
<a name="l00599"></a>00599     newly-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a> = victim-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a>;
<a name="l00600"></a>00600 }
<a name="l00601"></a>00601 
<a name="l00608"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gaa1f82a5e29f572f748a7f76381bb5887">00608</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gaa1f82a5e29f572f748a7f76381bb5887" title="交换两个树">avllnk_swap</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* a, <a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* b)
<a name="l00609"></a>00609 {
<a name="l00610"></a>00610     avllnk_iter t = a-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a>; a-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a> = b-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a>; b-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a> = t;
<a name="l00611"></a>00611 }
<a name="l00612"></a>00612 
<a name="l00622"></a>00622 NV_API <span class="keywordtype">int</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga704200059c0476fc18782999861d6a14" title="判断一个节点是否存在于树中">avllnk_exist</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, avllnk_iter itr);
<a name="l00623"></a>00623 
<a name="l00632"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gaf3d1abe7c6b78a506b4d3ba41c9e6c27">00632</a> <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#gaf3d1abe7c6b78a506b4d3ba41c9e6c27" title="得到正向索引对应的节点的迭代器">avllnk_at</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, <span class="keywordtype">size_t</span> index)
<a name="l00633"></a>00633 {
<a name="l00634"></a>00634     <span class="keywordflow">return</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga3f0b2fc1c3ebdcafb623a3906b168ad3" title="给迭代器增加一段距离或减小一段距离">avllnk_advance</a>(<a class="code" href="group__AVL_xE6_xA0_x91.html#ga0db4502b30c43020bbb5fe927c7f9d0a" title="得到树的最左端节点">avllnk_front</a>(root), index);
<a name="l00635"></a>00635 }
<a name="l00636"></a>00636 
<a name="l00646"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga092e3ed44b3f98a818c234d87503ca73">00646</a> <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#ga092e3ed44b3f98a818c234d87503ca73" title="得到逆向索引对应的节点的迭代器">avllnk_reverse_at</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, <span class="keywordtype">size_t</span> index)
<a name="l00647"></a>00647 {
<a name="l00648"></a>00648     <span class="keywordflow">return</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga3f0b2fc1c3ebdcafb623a3906b168ad3" title="给迭代器增加一段距离或减小一段距离">avllnk_advance</a>(<a class="code" href="group__AVL_xE6_xA0_x91.html#ga1634f51b55974ba696e962491ebc4eed" title="得到树的最右端节点">avllnk_back</a>(root), -(<span class="keywordtype">int</span>)(index));
<a name="l00649"></a>00649 }
<a name="l00650"></a>00650 
<a name="l00658"></a>00658 NV_API avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#ga0db4502b30c43020bbb5fe927c7f9d0a" title="得到树的最左端节点">avllnk_front</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root);
<a name="l00659"></a>00659 
<a name="l00667"></a>00667 NV_API avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#ga1634f51b55974ba696e962491ebc4eed" title="得到树的最右端节点">avllnk_back</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root);
<a name="l00668"></a>00668 
<a name="l00676"></a>00676 NV_API avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#gab06d7fe0465e53f4d47490bcdc59ccf4" title="得到当前节点的中序后继节点">avllnk_next</a>(avllnk_iter cur);
<a name="l00677"></a>00677 
<a name="l00685"></a>00685 NV_API avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#ga7311b77daeb0f3c6b467e57207014ccc" title="得到当前节点的中序前驱节点">avllnk_prev</a>(avllnk_iter cur);
<a name="l00686"></a>00686 
<a name="l00694"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga792e1e4f83bba2aad61546629e7ca033">00694</a> <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#ga792e1e4f83bba2aad61546629e7ca033" title="得到指向正向起始位置的迭代器">avllnk_begin</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root)
<a name="l00695"></a>00695 {
<a name="l00696"></a>00696     <span class="keywordflow">return</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga0db4502b30c43020bbb5fe927c7f9d0a" title="得到树的最左端节点">avllnk_front</a>(root);
<a name="l00697"></a>00697 }
<a name="l00698"></a>00698 
<a name="l00705"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga7bddf514252b09ff2b139cda1178d211">00705</a> <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#ga7bddf514252b09ff2b139cda1178d211" title="得到指向正向终止位置的迭代器">avllnk_end</a>()
<a name="l00706"></a>00706 {
<a name="l00707"></a>00707     <span class="keywordflow">return</span> NULL;
<a name="l00708"></a>00708 }
<a name="l00709"></a>00709 
<a name="l00717"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gac02afe94da5c646280f522904dff848d">00717</a> <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#gac02afe94da5c646280f522904dff848d" title="得到当前迭代器的正向终止位置">avllnk_end_of</a>(avllnk_iter cur)
<a name="l00718"></a>00718 {
<a name="l00719"></a>00719     <span class="keywordflow">return</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gab06d7fe0465e53f4d47490bcdc59ccf4" title="得到当前节点的中序后继节点">avllnk_next</a>(cur);
<a name="l00720"></a>00720 }
<a name="l00721"></a>00721 
<a name="l00729"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gaaedf1042b54f902d06e8c685e0b95385">00729</a> <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#gaaedf1042b54f902d06e8c685e0b95385" title="得到指向逆向起始位置的迭代器">avllnk_rbegin</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root)
<a name="l00730"></a>00730 {
<a name="l00731"></a>00731     <span class="keywordflow">return</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga1634f51b55974ba696e962491ebc4eed" title="得到树的最右端节点">avllnk_back</a>(root);
<a name="l00732"></a>00732 }
<a name="l00733"></a>00733 
<a name="l00740"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga5aa03d10a252d96ef9e7b478eb59ee66">00740</a> <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#ga5aa03d10a252d96ef9e7b478eb59ee66" title="得到指向逆向终止位置的迭代器">avllnk_rend</a>()
<a name="l00741"></a>00741 {
<a name="l00742"></a>00742     <span class="keywordflow">return</span> NULL;
<a name="l00743"></a>00743 }
<a name="l00744"></a>00744 
<a name="l00752"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gaebf7a263a0ac2f82ffe2c12c854b420c">00752</a> <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#gaebf7a263a0ac2f82ffe2c12c854b420c" title="得到当前迭代器的逆向终止位置">avllnk_rend_of</a>(avllnk_iter cur)
<a name="l00753"></a>00753 {
<a name="l00754"></a>00754     <span class="keywordflow">return</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#ga7311b77daeb0f3c6b467e57207014ccc" title="得到当前节点的中序前驱节点">avllnk_prev</a>(cur);
<a name="l00755"></a>00755 }
<a name="l00756"></a>00756 
<a name="l00764"></a>00764 NV_API avllnk_iter <a class="code" href="group__AVL_xE6_xA0_x91.html#ga3f0b2fc1c3ebdcafb623a3906b168ad3" title="给迭代器增加一段距离或减小一段距离">avllnk_advance</a>(avllnk_iter cur, <span class="keywordtype">int</span> dist);
<a name="l00765"></a>00765 
<a name="l00776"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gad10426452390142d32dc1a24eb538dbe">00776</a> <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="group__AVL_xE6_xA0_x91.html#gad10426452390142d32dc1a24eb538dbe" title="清空树">avllnk_clear</a>(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, <a class="code" href="group__AVL_xE6_xA0_x91.html#ga6d7aaed44e837466148513a1e9c4b055" title="单参数回调函数指针">avllnk_pr1</a> erase_handler)
<a name="l00777"></a>00777 {
<a name="l00778"></a>00778     <span class="keywordflow">if</span> (!<a class="code" href="group__AVL_xE6_xA0_x91.html#gaed7a979e936d126bdfcb326e7c341853" title="判断树是否为空">avllnk_empty</a>(root))
<a name="l00779"></a>00779         <a class="code" href="group__AVL_xE6_xA0_x91.html#ga062945f5da72bea1f96c1e79b14ee1d6" title="移除区域内的节点">avllnk_erases</a>(root, <a class="code" href="group__AVL_xE6_xA0_x91.html#ga0db4502b30c43020bbb5fe927c7f9d0a" title="得到树的最左端节点">avllnk_front</a>(root), NULL, erase_handler);
<a name="l00780"></a>00780 }
<a name="l00781"></a>00781 
<a name="l00782"></a>00782 <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter __avllnk_inc_later(avllnk_iter cur, avllnk_iter* p)
<a name="l00783"></a>00783 {
<a name="l00784"></a>00784     *p = <a class="code" href="group__AVL_xE6_xA0_x91.html#gab06d7fe0465e53f4d47490bcdc59ccf4" title="得到当前节点的中序后继节点">avllnk_next</a>(cur);
<a name="l00785"></a>00785     <span class="keywordflow">return</span> cur;
<a name="l00786"></a>00786 }
<a name="l00787"></a>00787 
<a name="l00788"></a>00788 <span class="keyword">static</span> <span class="keyword">inline</span> avllnk_iter __avllnk_dec_later(avllnk_iter cur, avllnk_iter* p)
<a name="l00789"></a>00789 {
<a name="l00790"></a>00790     *p = <a class="code" href="group__AVL_xE6_xA0_x91.html#ga7311b77daeb0f3c6b467e57207014ccc" title="得到当前节点的中序前驱节点">avllnk_prev</a>(cur);
<a name="l00791"></a>00791     <span class="keywordflow">return</span> cur;
<a name="l00792"></a>00792 }
<a name="l00793"></a>00793 
<a name="l00804"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga46ed1ab24644d90c5e70a413f455e670">00804</a> <span class="preprocessor">#define avllnk_inc(itr)         ((itr) = avllnk_next(itr))</span>
<a name="l00805"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga16e3c0d56368448f31d026003b3c8f74">00805</a> <span class="preprocessor"></span><span class="preprocessor">#define avllnk_dec(itr)         ((itr) = avllnk_prev(itr))</span>
<a name="l00806"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gaa5d4560ed66c6bce1884a391b0cef501">00806</a> <span class="preprocessor"></span><span class="preprocessor">#define avllnk_inc_later(itr)   __avllnk_inc_later(itr, &amp;(itr))</span>
<a name="l00807"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga2099017c69df209a020ecad6c50130b0">00807</a> <span class="preprocessor"></span><span class="preprocessor">#define avllnk_dec_later(itr)   __avllnk_dec_later(itr, &amp;(itr))</span>
<a name="l00808"></a>00808 <span class="preprocessor"></span>
<a name="l00818"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga4d808bbb0fdc74ca311dfcd3501a72ab">00818</a> <span class="preprocessor">#define avllnk_foreach(_begin, _end, fn, type, member) do {\</span>
<a name="l00819"></a>00819 <span class="preprocessor">        avllnk_iter _q_e = (_end);                          \</span>
<a name="l00820"></a>00820 <span class="preprocessor">        avllnk_iter _q_f = (_begin);                        \</span>
<a name="l00821"></a>00821 <span class="preprocessor">        while (_q_f != _q_e) {                              \</span>
<a name="l00822"></a>00822 <span class="preprocessor">            type * _q_t = container_of(_q_f, type, member); \</span>
<a name="l00823"></a>00823 <span class="preprocessor">            avllnk_inc(_q_f);                               \</span>
<a name="l00824"></a>00824 <span class="preprocessor">            fn(_q_t);                                       \</span>
<a name="l00825"></a>00825 <span class="preprocessor">        }                                                   \</span>
<a name="l00826"></a>00826 <span class="preprocessor">    } while (0)</span>
<a name="l00827"></a>00827 <span class="preprocessor"></span>
<a name="l00837"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga90c6c4362d26d8f4018fe435cb6f997c">00837</a> <span class="preprocessor">#define avllnk_reverse_foreach(_rbegin, _rend, fn, type, member) do {\</span>
<a name="l00838"></a>00838 <span class="preprocessor">        avllnk_iter _q_e = (_rend);                         \</span>
<a name="l00839"></a>00839 <span class="preprocessor">        avllnk_iter _q_f = (_rbegin);                       \</span>
<a name="l00840"></a>00840 <span class="preprocessor">        while (_q_f != _q_e) {                              \</span>
<a name="l00841"></a>00841 <span class="preprocessor">            type * _q_t = container_of(_q_f, type, member); \</span>
<a name="l00842"></a>00842 <span class="preprocessor">            avllnk_dec(_q_f);                               \</span>
<a name="l00843"></a>00843 <span class="preprocessor">            fn(_q_t);                                       \</span>
<a name="l00844"></a>00844 <span class="preprocessor">        }                                                   \</span>
<a name="l00845"></a>00845 <span class="preprocessor">    } while (0)</span>
<a name="l00846"></a>00846 <span class="preprocessor"></span>
<a name="l00847"></a>00847 NV_API <span class="keywordtype">void</span> __do_avllnk_recurse_foreach(
<a name="l00848"></a>00848                 avllnk_iter cur, <span class="keywordtype">void</span> (*fn)(<span class="keywordtype">void</span>*), <span class="keywordtype">size_t</span> offset);
<a name="l00849"></a>00849 
<a name="l00850"></a>00850 NV_API <span class="keywordtype">void</span> __do_avllnk_recurse_reverse_foreach(
<a name="l00851"></a>00851                 avllnk_iter cur, <span class="keywordtype">void</span> (*fn)(<span class="keywordtype">void</span>*), <span class="keywordtype">size_t</span> offset);
<a name="l00852"></a>00852 
<a name="l00853"></a>00853 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> __avllnk_recurse_foreach(
<a name="l00854"></a>00854     <a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, <span class="keywordtype">void</span> (*fn)(<span class="keywordtype">void</span>*), <span class="keywordtype">size_t</span> offset)
<a name="l00855"></a>00855 {
<a name="l00856"></a>00856     <span class="keywordflow">if</span> (fn)
<a name="l00857"></a>00857         __do_avllnk_recurse_foreach(root-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a>, fn, offset);
<a name="l00858"></a>00858 }
<a name="l00859"></a>00859 
<a name="l00860"></a>00860 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> __avllnk_recurse_reverse_foreach(
<a name="l00861"></a>00861     <a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, <span class="keywordtype">void</span> (*fn)(<span class="keywordtype">void</span>*), <span class="keywordtype">size_t</span> offset)
<a name="l00862"></a>00862 {
<a name="l00863"></a>00863     <span class="keywordflow">if</span> (fn)
<a name="l00864"></a>00864         __do_avllnk_recurse_reverse_foreach(root-&gt;<a class="code" href="structavllnk__root.html#a6470b4dbb19f6e6bc4cd94e01400c4ff" title="树根节点">node</a>, fn, offset);
<a name="l00865"></a>00865 }
<a name="l00866"></a>00866 
<a name="l00875"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga735253b77b7c2aec0f7bc17680d1035d">00875</a> <span class="preprocessor">#define AVLLNK_RECURSE_PROC(name, type, param) void name(type * param)</span>
<a name="l00876"></a>00876 <span class="preprocessor"></span>
<a name="l00900"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gad56775ebcd996a1da4be44d5f4963c91">00900</a> <span class="preprocessor">#define avllnk_recurse_foreach(root, fn, type, member) \</span>
<a name="l00901"></a>00901 <span class="preprocessor">    __avllnk_recurse_foreach(root, (void (*)(void*))(fn), \</span>
<a name="l00902"></a>00902 <span class="preprocessor">        offset_of(type, member))</span>
<a name="l00903"></a>00903 <span class="preprocessor"></span>
<a name="l00913"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga754839960ffe6023b3c85a88a456a774">00913</a> <span class="preprocessor">#define avllnk_recurse_reverse_foreach(root, fn, type, member) \</span>
<a name="l00914"></a>00914 <span class="preprocessor">    __avllnk_recurse_reverse_foreach(root, (void (*)(void*))(fn), \</span>
<a name="l00915"></a>00915 <span class="preprocessor">            offset_of(type, member))</span>
<a name="l00916"></a>00916 <span class="preprocessor"></span>
<a name="l00945"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gaff35c890d83519b776a6186a94ad29ac">00945</a> <span class="preprocessor">#define avllnk_search(root, newly, greater, res, type, member) do {\</span>
<a name="l00946"></a>00946 <span class="preprocessor">        avllnk_root* _k_r = (root);                             \</span>
<a name="l00947"></a>00947 <span class="preprocessor">        type * _k_pn = (newly);                                 \</span>
<a name="l00948"></a>00948 <span class="preprocessor">        avllnk_iter _k_p = _k_r-&gt;node;                          \</span>
<a name="l00949"></a>00949 <span class="preprocessor">        (res) = NULL;                                           \</span>
<a name="l00950"></a>00950 <span class="preprocessor">        while (_k_p) {                                          \</span>
<a name="l00951"></a>00951 <span class="preprocessor">            type * _k_pr = container_of(_k_p, type, member);    \</span>
<a name="l00952"></a>00952 <span class="preprocessor">            if (greater(_k_pr, _k_pn))                          \</span>
<a name="l00953"></a>00953 <span class="preprocessor">                _k_p = _k_p-&gt;left;                              \</span>
<a name="l00954"></a>00954 <span class="preprocessor">            else if (greater(_k_pn, _k_pr))                     \</span>
<a name="l00955"></a>00955 <span class="preprocessor">                _k_p = _k_p-&gt;right;                             \</span>
<a name="l00956"></a>00956 <span class="preprocessor">            else {                                              \</span>
<a name="l00957"></a>00957 <span class="preprocessor">                (res) = _k_p; break;                            \</span>
<a name="l00958"></a>00958 <span class="preprocessor">            }                                                   \</span>
<a name="l00959"></a>00959 <span class="preprocessor">        }                                                       \</span>
<a name="l00960"></a>00960 <span class="preprocessor">    } while (0)</span>
<a name="l00961"></a>00961 <span class="preprocessor"></span>
<a name="l00990"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#gaa70312544a3ecfb8d51680b04ba1c745">00990</a> <span class="preprocessor">#define avllnk_insert(root, newly, greater, res, type, member) do {\</span>
<a name="l00991"></a>00991 <span class="preprocessor">        avllnk_root* _k_r = (root);                                     \</span>
<a name="l00992"></a>00992 <span class="preprocessor">        avllnk_iter* _k_pp = &amp;_k_r-&gt;node;                               \</span>
<a name="l00993"></a>00993 <span class="preprocessor">        avllnk_iter _k_n = (newly);                                     \</span>
<a name="l00994"></a>00994 <span class="preprocessor">        avllnk_iter _k_p;                                               \</span>
<a name="l00995"></a>00995 <span class="preprocessor">        type * _k_pn = container_of(_k_n, type, member);                \</span>
<a name="l00996"></a>00996 <span class="preprocessor">        (res) = 1;                                                      \</span>
<a name="l00997"></a>00997 <span class="preprocessor">        avllnk_node_init(_k_n);                                         \</span>
<a name="l00998"></a>00998 <span class="preprocessor">        while (*_k_pp) {                                                \</span>
<a name="l00999"></a>00999 <span class="preprocessor">            type * _k_pr = container_of(_k_p = *_k_pp, type, member);   \</span>
<a name="l01000"></a>01000 <span class="preprocessor">            if (greater(_k_pr, _k_pn))                                  \</span>
<a name="l01001"></a>01001 <span class="preprocessor">                _k_pp = &amp;_k_p-&gt;left;                                    \</span>
<a name="l01002"></a>01002 <span class="preprocessor">            else if (greater(_k_pn, _k_pr))                             \</span>
<a name="l01003"></a>01003 <span class="preprocessor">                _k_pp = &amp;_k_p-&gt;right;                                   \</span>
<a name="l01004"></a>01004 <span class="preprocessor">            else {                                                      \</span>
<a name="l01005"></a>01005 <span class="preprocessor">                (res) = 0; break;                                       \</span>
<a name="l01006"></a>01006 <span class="preprocessor">            }                                                           \</span>
<a name="l01007"></a>01007 <span class="preprocessor">        }                                                               \</span>
<a name="l01008"></a>01008 <span class="preprocessor">        if (res) {                                                      \</span>
<a name="l01009"></a>01009 <span class="preprocessor">            avllnk_link(_k_n, _k_p, _k_pp);                             \</span>
<a name="l01010"></a>01010 <span class="preprocessor">            avllnk_rebalance(_k_r, _k_n, _k_p);                         \</span>
<a name="l01011"></a>01011 <span class="preprocessor">        }                                                               \</span>
<a name="l01012"></a>01012 <span class="preprocessor">    } while (0)</span>
<a name="l01013"></a>01013 <span class="preprocessor"></span>
<a name="l01014"></a>01014 NV_API <span class="keywordtype">void</span> __avllnk_serialize(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, <span class="keywordtype">void</span>** buf, <span class="keywordtype">size_t</span> offset);
<a name="l01015"></a>01015 
<a name="l01016"></a>01016 NV_API <span class="keywordtype">void</span> __avllnk_deserialize(<a class="code" href="structavllnk__root.html" title="树根">avllnk_root</a>* root, <span class="keywordtype">void</span>** buf, 
<a name="l01017"></a>01017                                  <span class="keywordtype">size_t</span> cnt, <span class="keywordtype">size_t</span> offset);
<a name="l01018"></a>01018 
<a name="l01019"></a>01019 
<a name="l01029"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga6ef8f29070186c926ea5202dd2be868b">01029</a> <span class="preprocessor">#define avllnk_serialize(root, buf, type, member) \</span>
<a name="l01030"></a>01030 <span class="preprocessor">    __avllnk_serialize(root, (void**)(buf), offset_of(type, member))</span>
<a name="l01031"></a>01031 <span class="preprocessor"></span>
<a name="l01042"></a><a class="code" href="group__AVL_xE6_xA0_x91.html#ga48ba9521f27bb0961ac4b2d5af927732">01042</a> <span class="preprocessor">#define avllnk_deserialize(root, buf, cnt, type, member) \</span>
<a name="l01043"></a>01043 <span class="preprocessor">    __avllnk_deserialize(root, (void**)(buf), cnt, offset_of(type, member))</span>
<a name="l01044"></a>01044 <span class="preprocessor"></span>
<a name="l01047"></a>01047 <span class="preprocessor">#ifdef __cplusplus</span>
<a name="l01048"></a>01048 <span class="preprocessor"></span>}
<a name="l01049"></a>01049 <span class="preprocessor">#endif  </span><span class="comment">/* #ifdef __cplusplus */</span>
<a name="l01050"></a>01050 
<a name="l01051"></a>01051 <span class="preprocessor">#endif </span><span class="comment">/* #ifndef __NV_AVLLNK__ */</span>
<a name="l01052"></a>01052 
</pre></div></div>
</div>
<!--- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>全部</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>数据结构</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>文件</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>函数</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>变量</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>类型定义</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>宏定义</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<hr class="footer"/><address class="footer"><small>Generated at 2015年七月16日 星期四 12:00:37 for Navo Portable Library by&#160;
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.3 </small></address>
</body>
</html>
